package week_08;


public class ImplementStrstr_demo_28 {
    // 实现robin-krap算法
    //𝐻[𝑖]=Hash(𝑠[0...𝑖−1])= 𝐻[𝑖−1]∗𝑏+[𝑠𝑖−1]mod 𝑝
    //𝐻[5]–𝐻[2]∗𝑏3
    //fooba−fo000=oba
    //Hash(𝑠𝑙...𝑟)=(𝐻[𝑟+1]−𝐻[𝑙]∗(pow(𝑏,𝑟−𝑙+1) )mod 𝑝
    //O(1) 时间复杂度
    int b = 131;
    int p = (int) (1e9 + 7);

    public int strStr(String haystack, String needle) {

        // 计算前i个字符的hash值
        int n = haystack.length();
        int m = needle.length();
        if (n == 0 && m == 0) return 0;
        if (n < m) return -1;
        char[] s = haystack.toCharArray();
        char[] t = needle.toCharArray();
        long[] h = new long[n + 1];
        h[0] = 0;
        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * b + s[i] - 'a' + 1) % p;
        }
        long THASH = 0;
        for (int i = 0; i < m; i++) {
            THASH = (THASH * b + t[i] - 'a' + 1) % p;
        }

        // 计算s中m长度的子串的hash值是否相等THASH
        for (int i = m - 1; i < n; i++) {
            System.out.println(subHash(i - m + 1, i, h));
            if (subHash(i - m + 1, i, h) == THASH) return i-1;
        }

        return -1;
    }

    public int subHash(int l, int r, long[] h) {
        return (int) ((h[r + 1] - h[l] * Math.pow(b, r - l + 1)) % p + p) % p;
    }


    public int strStr2(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (n == 0 && m == 0) return 0;
        for (int i = 0; i < n; i++) {
            int idx = 0;
            while (idx < m && idx + i < n && haystack.charAt(i + idx) == needle.charAt(idx)) {
                //  System.out.println(haystack.charAt(i+idx)+":"+needle.charAt(idx)+":"+i+":"+idx);
                idx++;
            }
            // idx 加了多少次 就是多长的字符串
            if (idx == m) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        String s1 = "hello";
        String s2 = "ll";
        ImplementStrstr_demo_28 test = new ImplementStrstr_demo_28();
        System.out.println(test.strStr(s1, s2));
        ;
    }
}
